#include <string.h>
#include <math.h>
#include <stack>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
using namespace std;

int priority(char c)
{
    switch (c) {
    case '#':
        return 0;
    case '^':
        return 1;
    case '*':
    case '/':
        return 2;
    case '+':
    case '-':
        return 3;
    }
    return -1;
}

struct math_object
{
    enum type { unknown = 0, ops, number, symbol } t;
    union {
        char op;
        int num;
        char *sym;
    };
};

void str2objs(const string &s, vector<math_object> &objs)
{
    int len = s.length();
    for (int i = 0; i < len; i++) {
        math_object obj;
        obj.t = math_object::unknown;
        if (s[i] == ' ') {
            continue;
        } else if (s[i] == '(' || s[i] == ')' || s[i] == '^'
            || s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
            obj.t = math_object::ops;
            obj.op = s[i];
        } else if (s[i] >= '0' && s[i] <= '9') {
            obj.t = math_object::number;
            obj.num = 0;
            while (i < len && s[i] >= '0' && s[i] <= '9') {
                obj.num = obj.num*10 + s[i] - '0';
                i++;
            }
            i--;
        } else if (s[i] >= 'a' && s[i] <= 'z') {
            obj.t = math_object::symbol;
            string sym;
            while (i < len && s[i] >= 'a' && s[i] <= 'z') {
                sym += s[i];
                i++;
            }
            obj.sym = strdup(sym.c_str());
            i--;
        }
        if (obj.t != math_object::unknown) {
            objs.push_back(obj);
        }
    }
}

bool infix_to_postfix(const vector<math_object> &in, vector<math_object> &out)
{
    stack<math_object> ops;
    for (vector<math_object>::const_iterator it = in.begin(); it != in.end(); ++it) {
        if (it->t == math_object::ops) {
            if (it->op == '(') {
                ops.push(*it);
            } else if (it->op == ')') {
                bool find = false;
                while (!ops.empty()) {
                    math_object obj = ops.top();
                    ops.pop();
                    if (obj.op == '(') {
                        find = true;
                        break;
                    }
                    out.push_back(obj);
                }
                if (!find) {
                    cout << "ERROR: cannot find \'(\'." << endl;
                    return false;
                }
            } else {
                while (!ops.empty()) {
                    math_object obj = ops.top();
                    if (obj.op == '(') {
                        break;
                    }
                    if (priority(it->op) < priority(obj.op)) {
                        break;
                    }
                    out.push_back(obj);
                    ops.pop();
                }
                ops.push(*it);
            }
        } else if (it->t == math_object::number || it->t == math_object::symbol) {
            out.push_back(*it);
        }
    }
    /* add remaining */
    while (!ops.empty()) {
        math_object obj = ops.top();
        ops.pop();
        if (obj.op == '(') {
            break;
        }
        out.push_back(obj);
    }
    return true;
}

bool postfix_to_infix(const vector<math_object> &in, string &out)
{
    stack<char> ops;
    stack<string> strs;
    for (vector<math_object>::const_iterator it = in.begin(); it != in.end(); ++it) {
        if (it->t == math_object::ops) {
            if (strs.size() < 2) {
                cout << "ERROR: missing operands." << endl;
                return false;
            }
            string str1, str2;
            str1 = strs.top();
            strs.pop();
            str2 = strs.top();
            strs.pop();
            char op1, op2;
            op1 = ops.top();
            ops.pop();
            op2 = ops.top();
            ops.pop();
            if (priority(it->op) < priority(op2)) {
                str2 = "(" + str2 + ")";
            }
            if (priority(it->op) < priority(op1)) {
                str1 = "(" + str1 + ")";
            }
            string res = str2 + it->op + str1;
            strs.push(res);
            ops.push(it->op);
        } else if (it->t == math_object::number || it->t == math_object::symbol) {
            string s;
            if (it->t == math_object::symbol) {
                s = it->sym;
            } else {
                stringstream ss;
                ss << it->num;
                ss >> s;
            }
            strs.push(s);
            ops.push('#');
        }
    }
    if (strs.size() == 1) {
        out = strs.top();
        return true;
    }
    return false;
}

bool postfix_eval(const vector<math_object> &in, int &out)
{
    stack<int> vals;
    for (vector<math_object>::const_iterator it = in.begin(); it != in.end(); ++it) {
        if (it->t == math_object::ops) {
            if (vals.size() < 2) {
                cout << "ERROR: missing operands." << endl;
                return false;
            }
            int v1, v2, v;
            v1 = vals.top();
            vals.pop();
            v2 = vals.top();
            vals.pop();
            switch (it->op) {
            case '^':
                v = pow(v2, v1);
                break;
            case '+':
                v = v2 + v1;
                break;
            case '-':
                v = v2 - v1;
                break;
            case '*':
                v = v2 * v1;
                break;
            case '/':
                v = v2 / v1;
                break;
            }
            vals.push(v);
        } else if (it->t == math_object::number) {
            vals.push(it->num);
        } else if (it->t == math_object::symbol) {
            cout << "ERROR: numbers only..." << endl;
            return false;
        }
    }
    if (vals.size() == 1) {
        out = vals.top();
        return true;
    }
    return false;
}

void print_math_objs(const vector<math_object> &objs)
{
    for (vector<math_object>::const_iterator it = objs.begin(); it != objs.end(); ++it) {
        switch (it->t) {
        case math_object::ops:
            cout << "ops: " << it->op << endl;
            break;
        case math_object::number:
            cout << "number: " << it->num << endl;
            break;
        case math_object::symbol:
            cout << "symbol: " << it->sym << endl;
            break;
        }
    }
}

int main(int argc, char *argv[])
{
#if 0
    string s = "(32+((1*2)+(23+7)*(7+5))*6)";
    cout << "==== infix ====" << endl;
    vector<math_object> objs;
    str2objs(s, objs);
    print_math_objs(objs);
    cout << "==== postfix ====" << endl;
    vector<math_object> postfix;
    infix_to_postfix(objs, postfix);
    print_math_objs(postfix);
    cout << "==== infix again ====" << endl;
#else
    cout << "input: ";
    string s;
    cin >> s;
    vector<math_object> objs;
    str2objs(s, objs);
    vector<math_object> postfix;
    infix_to_postfix(objs, postfix);
#endif
    string infix;
    if (postfix_to_infix(postfix, infix)) {
        cout << "simplified: " << infix << endl;
    }
    int value;
    if (postfix_eval(postfix, value)) {
        cout << "result: " << value << endl;
    }
    return 0;
}
